//描述
//从前序与中序遍历序列构造二叉树
class Solution {
    //prebegin成为成员变量，使其不会回溯
    public static int prebegin = 0;
    public static TreeNode buildTree(String preorder, String inorder) {
        return buildTreeChild(preorder, inorder, 0, inorder.length() - 1);
    }

    public static TreeNode buildTreeChild(String preorder, String inorder,int inbengin, int inend){
        //递归出口
        if (inbengin > inend) return null;
        //设置根节点
        TreeNode root = new TreeNode(preorder.charAt(prebegin));
        //在中序遍历中寻找根节点位置
        int rootpos = findPos(inorder, inbengin, inend, preorder.charAt(prebegin));
        prebegin++;
        //建立根节点的左子树和右子树
        root.left = buildTreeChild(preorder, inorder, inbengin, rootpos - 1);
        root.right = buildTreeChild(preorder, inorder, rootpos + 1 ,inend);
        return root;
    }
    //寻找根节点位置
    public static int  findPos(String inorder, int inbengin, int inend, int key){
        for (int i = inbengin; i <= inend; i++){
            if (inorder.charAt(i) == key){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String s = "EFHIGJK";
        String s1 = "HFIEJKG";
        TreeNode root = buildTree(s, s1);
        root.levelOrder(root);
    }
}